package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202411;

import com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241103.Leetcode3340;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class leetcode20241119 {

    /**
     * 新增道路查询后的最短距离I
     * 方法一：BFS，每次加边后，重新跑一边BFS
     * 方法二：DP算法
     * @param n
     * @param queries
     * @return
     */
//    public int[] shortestDistanceAfterQueries(int n,int[][] queries){
//        List<Integer>[] g=new ArrayList[n-1];
//        Arrays.setAll(g,i->new ArrayList<>());
//        for(int i=0;i<n-1;i++){
//            g[i].add(i+1);
//        }
//
//        int[] ans=new int[queries.length];
//        int[] vis=new int[n-1];
//        for(int i=0;i<queries.length;i++){
//            g[queries[i][0]].add(queries[i][1]);// 新增一条道路
//            ans[i]=bfs(i+1,g,vis,n);// 每次新增一条道路，重新进行bfs
//        }
//        return ans;
//    }
//
//    // 从0->n-1的最短距离
//    private int bfs(int i,List<Integer>[] g,int[] vis,int n){
//        List<Integer>q=new ArrayList<>();
//        q.add(0);
//        for(int step=1;;step++){
//            List<Integer> tmp=q;
//            q=new ArrayList<>();
//            for(int x : tmp){
//                for(int y : g[x]){
//                    if(y==n-1){
//                        return step;
//                    }
//                    if(vis[y]!=-1){
//                        vis[y]=i;
//                        q.add(y);
//                    }
//                }
//            }
//        }
//    }

    public int[] shortestDistanceAfterQueries(int n,int[][] queries){
        List<Integer>[] from=new ArrayList[n];
        Arrays.setAll(from,i->new ArrayList<>());
        int[] f=new int[n];
        for(int i=1;i<n;i++){
            f[i]=i;
        }

        int[] ans=new int[queries.length];
        for(int qi=0;qi<queries.length;qi++){
            int l=queries[qi][0];
            int r=queries[qi][1];
            from[r].add(l);
            if(f[l]+1<f[r]){
                f[r]=f[l]+1;
                for(int i=r+1;i<n;i++){
                    f[i]=Math.min(f[i],f[i-1]+1);
                    for(int j : from[i]){
                        f[i]=Math.min(f[i],f[j]+1);
                    }
                }
            }
            ans[qi]=f[n-1];
        }
        return ans;
    }

    public static void main(String[] args){
        leetcode20241119 leetcode20241119=new leetcode20241119();
        int n=5;
        int[][] queries={{2,4},{0,2},{0,4}};
        int[] ans=leetcode20241119.shortestDistanceAfterQueries(n,queries);
        for(int num : ans){
            System.out.println(num);
        }
    }
}
